package com.kingwood.algorithm.test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;

public class DanDiaoZhan {
    /**
     * 转盘寿司
     https://blog.csdn.net/qfc_128220/article/details/134495777
    寿司店周年庆，正在举办优惠活动回馈新老客户。
    寿司转盘上总共有 n 盘寿司，prices[i] 是第 i 盘寿司的价格，
    如果客户选择了第 i 盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j，前提是 prices[j]<prices[i]，如果没有满足条件的 j，则不赠送寿司。
    每个价格的寿司都可无限供应。
    **/

    public static void getCouponArray() {
        Scanner scanner = new Scanner(System.in);
        int[] prices = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer:: parseInt).toArray();
        int n = prices.length;

        int res[] = Arrays.copyOf(prices, n);

        // 单调栈，栈底到栈顶单调递增，压栈元素是栈顶元素在nums顺序后面的值
        // 每当压栈时，比较栈顶元素 > 压栈元素？若是，则说明找到了栈顶元素的下一个更小值，
        // 此时弹栈，压栈元素继续和新栈顶元素比较大小，直到栈顶元素 <= 压栈元素，则停止比较，执行压栈
        LinkedList<Integer> stack = new LinkedList<>(); // 栈中记录是prices元素的索引

        // 这里循环两轮，因为一轮循环可能无法确保所有值都能找到下一个更小值
        for (int j = 0; j < n * 2; j++) {
            // prices_j 是压栈(索引对应的)元素
            int prices_j = prices[j % n]; // 索引 j % n 是为了让第二轮遍历时，继续从prices的0索引开始

            while (stack.size() > 0) {
                // prices[i] 是栈顶(索引对应的)元素
                int i = stack.getLast();

                if (prices[i] > prices_j) {
                    // 如果栈顶元素 > 压栈元素，则说明找到了栈顶元素的下一个更小值，此时栈顶元素弹出,压栈元素继续和新的栈顶元素比较
                    stack.removeLast();
                    // 题目要统计当前元素和其下一个更小值元素之和
                    res[i] += prices_j;
                } else {
                    break;
                }
            }

            // 只有第一轮遍历时，才允许压栈，第二轮遍历时，只进行比较
            if (j < n) {
                stack.add(j);
            }
        }

        StringJoiner sj = new StringJoiner(" ");
        for (int num : res) {
            sj.add(num + "");
        }

        System.out.println(sj);
    }

    public static void getCouponArray2() {
        Scanner scanner = new Scanner(System.in);
        int[] prices = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = prices.length;
        int[] res = Arrays.copyOf(prices, n);
        LinkedList<Integer> stack = new LinkedList<>();

        for (int j = 0; j < n * 2; j++) {
            int prices_j = prices[j % n];

            while (stack.size() > 0) {
                int i = stack.getLast();
                if (prices[i] > prices_j) {
                    stack.removeLast();
                    res[i] += prices_j;
                } else {
                    break;
                }
            }

            if (j < n) {
                stack.add(j);
            }
        }

        StringJoiner sj = new StringJoiner(" ");
        for (int num : res) {
            sj.add(num + "");
        }

        System.out.println(sj);
        return;
    }

    /**
     *
     * 请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     * @param temperatures
     * @return
     */
    public static int MAIN = 100001;
    public static int[] stack = new int[MAIN];
    public static int r;

    public static  int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        r = 0;

        for (int i=0, cur; i<len; i++) {
            while (r>0 && temperatures[i] > temperatures[stack[r-1]]) {
                cur = stack[--r];
                ans[cur] = i - cur;
            }

            stack[r++] = i;
        }

        return ans;
    }

    public static int[] dailyTemperatures2(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        r = 0;

        for (int i=0, cur; i<len; i++) {
            //stack 从大到小排序
            while(r > 0 && temperatures[i] > temperatures[stack[r-1]]) {
                cur = stack[--r];
                ans[cur] = i - cur;
            }

            stack[r++] = i;
        }

        return ans;
    }

    public static void main(String[] args) {
        // getCouponArray();
//        getCouponArray2();
//        int[] temperatures = {30,40,50,60};
//        int[] res = dailyTemperatures2(temperatures);
//        System.out.println(Arrays.toString(res));

        // 航空公司缩写排序按照从特殊符号$ & *，0~9，A~Z排序；

        String[] strs = {"AZ", "BC", "AD", "91", "23", "$&"};
        Arrays.sort(strs);
        System.out.println(Arrays.toString(strs));

    }
}
